package com.wayne.leetcode.problems;

import java.util.ArrayDeque;
import java.util.Deque;

class Solution316 {
  public static String removeDuplicateLetters(String s) {
    char[] chars = s.toCharArray();
    boolean[] visited = new boolean[26];
    int[] lastIndex = new int[26];
    Deque<Character> stack = new ArrayDeque<>();
    for (int i = 0; i < s.length(); i++) {
      lastIndex[chars[i] - 'a'] = i;
    }
    for (int i = 0; i < s.length(); i++) {
      // 在栈里面忽略掉当前字符
      if (visited[chars[i] - 'a']) {
        continue;
      }
      // 当前的字符小于栈顶的元素 且 栈顶的元素后面还会出现
      while (!stack.isEmpty() && stack.peekLast() > chars[i] && lastIndex[stack.peekLast() - 'a'] > i) {
        Character top = stack.removeLast();
        visited[top - 'a'] = false;
      }
      stack.addLast(chars[i]);
      visited[chars[i] - 'a'] = true;
    }
    StringBuilder sb = new StringBuilder();
    for (char c : stack) {
      sb.append(c);
    }
    return sb.toString();
  }

  public static void main(String[] args) {
    System.out.println(removeDuplicateLetters("cbacdcbc"));
  }
}